#include <iostream>
#include <cstring>
#include <algorithm>
#include <regex>

using namespace std;

bool isMatch2(string s, string p) {
    string pattern = p;
    regex re(pattern);
    return regex_match(s,re);
}

bool isMatch1(const char *s, const char* p) {
    if(*p=='\0')return *s=='\0';
    bool firstMatch = *s!='\0'&&(*s==*p||*p=='.');

    if(p[1]=='*'){
        return isMatch1(s,p+2)||(firstMatch&&isMatch1(++s,p));
    }
    else{
        return firstMatch&&isMatch1(++s,++p);
    }
}

bool isMatch(string s,string p){
    return isMatch1(s.c_str(),p.c_str());
}

bool isMatch3(string s,string p){
    int slen = s.size(),plen = p.size();
    vector<vector<bool>>array(slen+1,vector<bool>(plen+1,false));

    array[0][0]=true;

    for(int i=0;i<plen;i++){
        if(p[i]=='*'){
            array[0][i+1]=array[0][i-1];
        }
    }

    for(int i=1;i<=slen;i++){
        for(int j=1;j<=plen;j++){
            if(s[i-1]==p[j-1]||p[j-1]=='.'){
                array[i][j]=array[i-1][j-1];
            }
            else if(p[j-1]=='*'){
                if(s[i-1]==p[j-2]||p[j-2]=='.'||s[i-1]==p[j-3]){
                    array[i][j]=array[i][j-1]||array[i-1][j]||array[i][j-2];
                }
                else array[i][j]=false;
            }
            else{
                array[i][j]=false;
            }
        }
    }
    return array[slen][plen];
}

int main(){
//    string pattern{".*b"};
//    regex re(pattern);
//    std::vector<std::string> str{ "cab", "ccccccaautfytcvygvaaaaaabbbbba", "aaaba"};
//
//    for(auto tmp:str){
//        bool ret=regex_match(tmp,re);
//        if(ret) cout<<tmp<<",can match"<<endl;
//        else cout<<tmp<<",can not match"<<endl;
//    }"bbbba"
//".*a*a"
    cout<<isMatch3("aasdfasdfasdfasdfas","aasdf.*asdf.*asdf.*asdf.*s")<<endl;
    return 0;
}